import java.util.Arrays;

public class Solution17_16 {
    public int getMax(int[] nums){
        int res=0;
        for (int num:nums) {
            res=Math.max(res,num);
        }
        return res;
    }

    public int massage(int[] nums) {
        if(nums.length<=2){
            return getMax(nums);
        }
        int[] dp=new int[nums.length];
        dp[0]=nums[0];
        dp[1]=Math.max(nums[1],nums[0]);
        for (int i = 2; i < nums.length; i++) {
            dp[i]=Math.max(dp[i-2]+nums[i],dp[i-1]);
        }
        return dp[nums.length-1];
    }

    public static void main(String[] args) {
        Solution17_16 s=new Solution17_16();
        System.out.println(s.massage(new int[]{2,1,1,2}));
    }
}
